package leetcode_core.leetcode_6;

import org.junit.Test;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月31日 19:22
 */
public class ReversePairs {
    private int count = 0;
    private int[] memo;
    public int reversePairs(int[] nums) {
        int n = nums.length;
        memo = new int[n];
        sort(nums,0,n-1);
        return count;
    }

    private void sort(int[] nums,int lo,int hi){
        if(lo == hi){return;}
        //后序遍历
        int mid = lo + ((hi - lo) >> 1);
        sort(nums,lo,mid);
        sort(nums,mid+1,hi);
        merge(nums,lo,mid,hi);
    }

    private void merge(int[] nums,int lo,int mid,int hi){
        for(int i = lo;i<=hi;i++){
            memo[i] = nums[i];
        }
        //做排序
        int i = lo;
        int j = mid+1;
        for(int p = lo;p<=hi;p++){
            if(i == mid+1){
                nums[p] = memo[j++];
            }else if(j == hi+1){
                nums[p] = memo[i++];
                //[mid+1,hi] = hi - mid -1 +1
                count += hi-mid;
            }else if(memo[i] <= memo[j]) {
                nums[p] = memo[i++];
                //[mid+1,j-1] = j-1 - mid -1 +1 = j-mid-1
                count += j-mid-1;
            }else{//memo[i] > memo[j]
                nums[p] = memo[j++];
            }
        }
    }
    @Test
    public void test(){
        System.out.println(reversePairs(new int[]{}));
    }
}
